import java.util.Arrays;

public class MyHeap {
    private int[] elem;
    private int usedSize;

    public MyHeap(){
        this.elem = new int[10];
    }

    public int[] getElem(){
        return this.elem;
    }

    public int getUsedSize(){
        return this.usedSize;
    }


    public void initElem(int[] arr){
        for(int i = 0; i < arr.length; i++){
            this.elem[i] = arr[i];
            this.usedSize++;
            if(isFull()){
                elem = Arrays.copyOf(elem, elem.length + 5);
            }
        }
    }

    // 创建大根堆
    public void createHeap(){
        for(int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent-- ){
            shiftDown(parent, usedSize);
        }
    }

    private void shiftDown(int parent, int len){
        // 起码有左孩子
        int child = 2 * parent + 1;
        while(child < len){
            // 保证 child 为左右孩子中，数值最大的孩子
            if(child + 1 < len && elem[child] < elem[child + 1]){
                child++;
            }

            if(elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }

    // 堆的插入
    public void insert(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem, elem.length + 5);
        }
        elem[usedSize++] = val;
        shiftUp(val, usedSize - 1);
    }
    private boolean isFull(){
        return elem.length == usedSize;
    }

    private void shiftUp(int val, int child){
        int parent = (child - 1) / 2;
        while(child > 0){
            if(elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    }

    // 堆的删除，只能从顶部删除
    public void delete(){
        if(isEmpty()){
            return;
        }

        elem[0] = elem[usedSize - 1];
        usedSize--;

        shiftDown(0, usedSize);

    }

    private boolean isEmpty(){
        return elem.length == 0;
    }


    // 堆的排序
    public void sort(){
        int end = usedSize - 1;
        while(end > 0){
            swap(elem, 0, end);
            shiftDown(0, end);
            end--;
        }
    }

    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Override
    public String toString() {
        return "MyHeap{" +
                "elem=" + Arrays.toString(elem) +
                '}';
    }
}
